Campus bikes II¶
Time: O(WxBx2^B); Space: O(WxBx2^B); medium
On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.
We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.
The Manhattan distance between two points p1 and p2 is:
Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.
Example 1:
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation:
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.
Example 2:
Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation:
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.
Constraints:
0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
All worker and bike locations are distinct.
1 <= len(workers) <= len(bikes) <= 10
Hints:
If w = b, we can even apply Hungarian algorithm (see https://en.wikipedia.org/wiki/Hungarian_algorithm),
It can be improved to O(w^3), see https://github.com/t3nsor/codebook/blob/master/bipartite-mincost.cpp
1. Dynamic Programming [O(WxBx2^B), O(WxBx2^B)]¶
Algorithm
For each worker, check which is the cloest bike, assign it to the worker. And check the next worker until we hit the end of worker list.
We could use state to record which bike has been used. say 01101 means bike 0, 2, 3 have been used because bit 0, 2, 3 are equal to 1.
Check bike i, if state & (1 << i) != 0, this means the bike i has been taken before.
Otherwise, we use this bike and accumlate the manhattan distance.
DFS state needs workers, worker index, bikes, current state and dp to record state. DFS returns minimum distance sum with current state.
[1]:
class Solution1(object): # this is slower than Solution2 in python
"""
Time: O(W*B*2^B)
Space: O(B*2^B)
"""
def assignBikes(self, workers, bikes):
"""
:type workers: List[List[int]]
:type bikes: List[List[int]]
:rtype: int
"""
def manhattan(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
dp = [[float("inf")]*((1<<len(bikes))) for _ in range(2)]
dp[0][0] = 0
for i in range(len(workers)):
dp[(i+1)%2] = [float("inf")] * ((1<<len(bikes)))
for j in range(len(bikes)):
for taken in range((1<<len(bikes))):
if taken & (1<<j):
continue
dp[(i+1)%2][taken|(1<<j)] = min(dp[(i+1)%2][taken|(1<<j)],
dp[i%2][taken] +
manhattan(workers[i], bikes[j]))
return min(dp[len(workers)%2])
[2]:
s = Solution1()
workers = [[0,0],[2,1]]
bikes = [[1,2],[3,3]]
assert s.assignBikes(workers, bikes) == 6
workers = [[0,0],[1,1],[2,0]]
bikes = [[1,0],[2,2],[2,1]]
assert s.assignBikes(workers, bikes) == 4
2. Using Heap¶
[3]:
import heapq
class Solution2(object):
def assignBikes(self, workers, bikes):
"""
:type workers: List[List[int]]
:type bikes: List[List[int]]
:rtype: int
"""
def manhattan(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
min_heap = [(0, 0, 0)]
lookup = set()
while min_heap:
cost, i, taken = heapq.heappop(min_heap)
if (i, taken) in lookup:
continue
lookup.add((i, taken))
if i == len(workers):
return cost
for j in range(len(bikes)):
if taken & (1<<j):
continue
heapq.heappush(min_heap, (cost+manhattan(workers[i], bikes[j]), # O(b)
i+1, # O(w)
taken|(1<<j))) # O(2^b)
[4]:
s = Solution2()
workers = [[0,0],[2,1]]
bikes = [[1,2],[3,3]]
assert s.assignBikes(workers, bikes) == 6
workers = [[0,0],[1,1],[2,0]]
bikes = [[1,0],[2,2],[2,1]]
assert s.assignBikes(workers, bikes) == 4